// 给定四个包含整数的数组列表 A , B , C , D ,计算有多少个元组 (i, j, k, l) ，
// 使得 A[i] + B[j] + C[k] + D[l] = 0。


const fourSumCount = function (A: number[], B: number[], C: number[], D: number[]) {
    const hashMap = new Map<number, number>();// 初始化哈希表
    // 以前两组为一组记录哈希表
    for (let i = 0; i < A.length; i++) {
        for (let j = 0; j < B.length; j++) {
            let key: number = A[i] + B[j];
            hashMap.set(key, (hashMap.get(key) || 0) + 1);
        }
    }
    let count = 0;
    // 后两组为一组
    for (let i = 0; i < C.length; i++) {
        for (let j = 0; j < D.length; j++) {
            // 算出结果在哈希表里面找
            let key: number = 0 - C[i] - D[j]
            if (hashMap.has(key)) {
                count += (hashMap.get(key) || 0);
            }
        }
    }
    return count;
};


fourSumCount([1, 2], [-2, -1], [-1, 2], [0, 2])


// 这道题目的设计如果能想到还是比较容易的，是一种分组或者说分桶的思想
// 我们把四组数组分成两组来处理，如A\B一组，C\D一组
// 我们计算每组数的和，用一个哈希表来存储，存储的过程中把和作为key
// key出现的次数作为value
// 然后再分组加和判断是否存在对应的key，如果存在的话计数变量就直接加上哈希表的value（次数）
// 这在一定程度上也节省访问的速度，并提高了计算的效率
// 其实当因数和情况更多的情况下也一样可以处理。

